package person.bing.fbcloud.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: mengfanbing
 * @date: 2020/9/11 9:14
 */
public class Q216 {
    public static void main(String[] args) {
        List<List<Integer>> ans = combinationSum3(1, 1);
        System.out.println(ans);
    }

    public static List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> combination = new ArrayList<>();
        for (int i=1;i<10;i++){
            combination.add(i);
        }
        util(ans,new ArrayList<>(),combination,0,k,n);
        return ans;
    }

    //遍历全组合
    public static void util(List<List<Integer>> ans,List<Integer> temp,List<Integer> combination,int startIndex,int k, int n) {
        if (startIndex >= combination.size()){
            if (temp.size() == k){
                Integer sum = temp.stream().reduce(Integer::sum).get();
                if (sum == n){
                    ans.add(new ArrayList<>(temp));
                }
            }
            return;
        }else {
            util(ans,temp,combination,startIndex+1,k,n);
            Integer value = combination.get(startIndex++);
            temp.add(value);
            util(ans,temp,combination,startIndex,k,n);
            temp.remove(Integer.valueOf(value));
        }
    }
}
